The use of asynchronous transfer mode (ATM) networks for the transfer of multimedia information, such as video, voice and data, has become increasingly popular due to the high data rate and flexibility associated with such networks. ATM networks utilize a cell-oriented switching and multiplexing technique, which has been specified by the International Telegraph and Telephone Consultative Committee (CCITT). For a general discussion of the CCITT standards, see M. dePrycker, Asynchronous Transfer Mode: Solutions from Broadband ISDN (Ellis Horwood, 1993). Generally, the ATM standard is based upon the use of short fixed-length "cells", comprised of a 48 byte payload information field, a four byte header field, containing routing and priority control information, and a one byte Header Error Control (HEC) field, containing a cyclic redundancy check (CRC), which serves to validate the header information.
ATM networks support connections of different bit rates, and allow bursty traffic to be integrated with continuous bit streams in a single network. Thus, ATM networks have been embraced by the computer and telecommunication industries for networking existing and future multimedia applications, such as video conferencing, video-on-demand, and telephone applications.
An ATM network is a connection-oriented network, in which each transfer of information between a source device and a destination device is preceded by a call to a network connection manager to establish a connection, often referred to as a virtual circuit, between the devices. Thus, the route between the devices is established prior to data transfer, and the connection is held during the entire transmission.
The basic concept in establishing an end-to-end connection in an ATM network is the request for a series of links from the source device to the destination device. The series of virtual channel links thus established is often referred to as a virtual channel connection (VCC). The virtual channel on each link of the overall connection is identified in each transmitted cell by a virtual channel identifier (VCI) in the cell header, as well as by a virtual path identifier (VPI), which identifies the virtual path to which the virtual channel belongs.
Thus, in order to route arriving cells, each switching node in an ATM network will typically include a routing translation table, which provides the VPI/VCI translation information for every cell going into the switching node. The relevant information for the routing translation table is entered during the call connection phase, and remains constant for the duration of a call.
The routing translation table may be implemented as a look-up table having an entry for each possible VPI/VCI combination. Since the VPI/VCI fields of an ATM cell header comprise 24 bits of information, the look-up table must have 2.sup.24 entries.
Although the large memory requirements for a direct look-up routing translation table may be justified for a switching node which handles a high volume of network traffic, such an implementation is clearly inefficient for a switching node handling lower traffic volume, such as a switching node near the periphery of the ATM network. For example, a leaf node in an ATM network, which may be embodied as a work station or other general purpose computing device, may only require ten active channels at any given time. Thus, of the 2.sup.24 entries in the leaf node's direct look-up routing table, only ten entries would be populated with routing information for an active connection.
In addition, a switching node must also typically separately process the cell header, which includes the VPI/VCI information, in order to validate the cell header information, by performing a cyclic redundancy check. If the CRC value calculated by the node for the received cell header matches the CRC value transmitted in the HEC field of the transmitted cell, the validity of the cell header information has been established.
As is apparent from the above discussion, a need exists for a more compact storage and retrieval system for storing the routing information utilized by switching nodes of an ATM network. In addition, a need exists for a routing information storage and retrieval system which validates the cell header information, while at the same time retrieving the necessary routing information from the routing translation table.